package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 二叉树的最大深度
 * @date 2025/2/20 22:11
 */
public class MaxDepth_104 {

    public static void main(String[] args) {
    }

    /**
     * 个解：递归-先序
     * <p>
     * maxDepth从0开始计算
     */
    int maxDepth7 = 0;

    public int maxDepth7(TreeNode root) {
        maxDepth6Recursion7(root, 0);
        return maxDepth7;
    }

    public void maxDepth6Recursion7(TreeNode root, int depth) {
        if (root == null) return;

        // 中
        // 记录本层的层级
        depth++;
        // 记录最大值
        maxDepth7 = Math.max(maxDepth7, depth);

        // 左
        maxDepth6Recursion7(root.left, depth);
        // 右
        maxDepth6Recursion7(root.right, depth);
    }

    /**
     * 个解-dfs-递归-前序
     * <p>
     * 思路：自上而下统计深度；单独记录每层深度，然后与全局变量最大深度比较，更新最大深度。
     */
    int maxDepth = 1;

    public int maxDepth6(TreeNode root) {
        if (root == null) return 0;

        maxDepth6Recursion6(root, 1);
        return maxDepth;
    }

    public void maxDepth6Recursion6(TreeNode root, int depth) {
        if (root == null) return;

        // 中
        // 先记录本层的maxDepth
        maxDepth = Math.max(maxDepth, depth);
        // 下一层
        depth++;

        // 左
        maxDepth6Recursion6(root.left, depth);
        // 右
        maxDepth6Recursion6(root.right, depth);
    }

    /**
     * 个解-dfs-递归-后序
     * <p>
     * 思路：转为求根节点的高度，从下往上计数。
     * <p>
     * 深度通常用前序遍历，为什么这里用后序？——因为，根节点的高度就是二叉树的最大深度，求高度则用后序遍历；该题可以转化为，求根节点的高度
     */
    public int maxDepth5(TreeNode root) {
        if (root == null) return 0;

        // 左
        int left = maxDepth5(root.left);
        // 右
        int right = maxDepth5(root.right);

        // 中
        int childMaxDepth = Math.max(left, right);
        return childMaxDepth + 1;
    }

    /**
     * 个解-BFS（同官解）；
     * 最大深度 = 层数
     */
    public int maxDepth3(TreeNode root) {
        if (root == null) return 0;

        // 最大深度 = 层数
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int maxDepth = 0;
        while (!queue.isEmpty()) {
            int curLayerSize = queue.size();
            for (int i = 0; i < curLayerSize; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
            maxDepth++;
        }
        return maxDepth;
    }

    /**
     * 自顶向下-leetcode他人题解；
     * 更满足从上到下统计个数的思维。
     */
    private int ans;

    public int maxDepth2(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        depth++;
        ans = Math.max(ans, depth);
        dfs(node.left, depth);
        dfs(node.right, depth);

        // 错误解法
       /* if (root == null) return 0;

        int curCount = nodeCounts++;
        int maxLeft = depth(root.left, nodeCounts);
        int maxRight = depth(root.right, curCount);
        int maxSon = Math.max(maxLeft, maxRight);

        return Math.max(maxLeft, maxRight);*/
    }

    /**
     * 官解（自底向上）
     * <p>
     * 分析：
     * <p>
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数；这里转为求高度
     * <p>
     * 那么，如果我们知道左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度 = max(l, r) + 1。
     * 为什么要 + 1？——因为max(l, r)得到的当前节点孩子中最长路径的节点数，还没有算上当前节点；而当本层循环结束，即返回上一层循环时，上一层的递归也在统计其孩子节点最长路径的节点数，所以要+1，把当前节点也统计上
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int maxLeft = maxDepth(root.left);
        int maxRight = maxDepth(root.right);

        // +1 是因为Math.max(maxLeft, maxRight)得到当前节点孩子节点的最长路径节点数，不包括当前节点，结束本层循环时需要统计当前节点，所以需要 +1。
        return Math.max(maxLeft, maxRight) + 1;
    }

}
